package 力扣日常刷题.木22二月.第05天211;

import 力扣日常刷题.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/2/11
 * @description
 */
public class Demo39二叉树中和为某个值的路径 {

    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return ans;
    }

    public void dfs(TreeNode cur, int target) {
        if (cur == null) return;
        path.offerLast(cur.val);
        target = target - cur.val;
        if (cur.left == null && cur.right == null && target == 0)
            ans.add(new LinkedList<>(path));
        dfs(cur.left, target);
        dfs(cur.right, target);
        path.pollLast();
    }
}
